package syntax

import utils.data.CTree
import scala.collection.mutable
import scala.collection.mutable.ArrayBuffer
import CSyntacticException._
import java.util.logging.Logger
import CGrammar.Lexeme2Terminal
import lexis.CLexeme

class CSyntacticAnalyzer(terminals:Seq[CTerminal],
                         nonTerminals:Seq[CNonTerminal],
                         start:CStart,
                         priorities:collection.Map[(CCategory, CCategory), CCategory],
                         lexemes:Seq[CLexeme],
                         lexemeToTerminal:(CLexeme)=>CTerminal)
{
    def apply():CTree[CASTNode] =
    {
        implicit val tree = CTree[CASTNode]()
        val t = System.currentTimeMillis
        val tbl = CTable(terminals:Seq[CTerminal], nonTerminals:Seq[CNonTerminal], start:CStart, priorities)
        println((System.currentTimeMillis - t)/1000d)
        println(tbl.size)

        val stts = mutable.Stack[Int](0)
        val ctgrs = mutable.Stack[CCategory]()
        val nds = mutable.Stack[CASTNode]()

        val lxms = mutable.Queue(lexemes:_*)

        while(true)
        {
            val trmnl:CTerminal = lxms.head
            val stt = stts.head
            tbl.getOrElse((stt, trmnl), CSyntacticException(GRAMMAR_ERROR)) match
            {
                case shft:CShift =>
                    stts.push(shft.state)
                    ctgrs.push(trmnl)
                    nds.push(CASTNode(trmnl, lxms.dequeue().value))
                case rds:CReduce =>
                    val nd = CASTNode(rds.category, rds.category.name)
                    tree.addNode(nd)
                    val rvrs = mutable.ArrayStack[CASTNode]()
                    for (_ <- 0 until rds.size)
                    {
                        stts.pop()
                        ctgrs.pop()
                        rvrs += nds.pop()
                    }
                    rvrs foreach nd.addNode
                    nds.push(nd)
                    ctgrs.push(rds.category)
                    if (ctgrs.top != start) stts.push(tbl(stts.head, rds.category).asInstanceOf[CGoTo].state)
                case _:CAccept => return tree
            }
        }
        null
    }
}

object CSyntacticAnalyzer
{
    def apply(terminals:Seq[CTerminal],
              nonTerminals:Seq[CNonTerminal],
              start:CStart,
              priorities:collection.Map[(CCategory, CCategory), CCategory],
              lexemes:Seq[CLexeme],
              lexemeToTerminal:(CLexeme)=>CTerminal) =
        (new CSyntacticAnalyzer(terminals, nonTerminals, start, priorities, lexemes, lexemeToTerminal))()
}

class CTable(terminals:Seq[CTerminal], nonTerminals:Seq[CNonTerminal], start:CStart, priorities:collection.Map[(CCategory, CCategory), CCategory])
{
    private val grammar = terminals ++ nonTerminals
    private val firstCache = mutable.HashMap[CCategory, Iterable[CCategory]]()
    private val closuresCache = mutable.HashMap[CSituationSet, CSituationSet]()
    private val gotoCache = new mutable.HashMap[(CSituationSet, CCategory), CSituationSet]()

    def apply() =
    {
        val actns = mutable.HashMap[(Int, CCategory), CAction]()

        val itms = items()
        val itmIndxs = mutable.HashMap(itms map (i => i -> itms.indexOf(i)):_*)

        for (i <- 0 until items.size)
        {
            itms(i).value foreach (s =>
            {
                if (s.isMarkerInBounds && s.isCurrentTerminal)
                {
                    val gt = goto(itms(i), s.current)
                    val j = itmIndxs.getOrElse(gt, -1)
                    if (j != -1)
                    {
                        if ((actns contains (i, s.current)) && actns((i, s.current)) != CShift(j)) CSyntacticException(UNRESOLVED_AMBIGUITY_DETECTED)
                        actns += (i, s.current) -> CShift(j)
                    }
                }
                else if (s.isMarkerInBounds && s.isStart) actns += (i, s.lookahead) -> CAccept()
                else if (!s.isMarkerInBounds)
                {
                    if (actns contains (i, s.lookahead))
                    {
                        val actn = actns((i, s.lookahead))
                        if (actn != CReduce(s.nonTerminal, s.size) && !actn.isInstanceOf[CShift])
                        {
                            if (actn.isInstanceOf[CReduce])
                            {
                                val rds = actn.asInstanceOf[CReduce]
                                val prrtt = priorities.getOrElse((rds.category, s.nonTerminal), priorities.getOrElse((s.nonTerminal, rds.category), CSyntacticException(UNRESOLVED_AMBIGUITY_DETECTED)))
                                Logger.getGlobal.warning(s"Ambiguity detected: ${s.nonTerminal} & ${rds.category}. $prrtt is prefered.")
                                if (prrtt == s.nonTerminal)
                                    actns += (i, s.lookahead) -> CReduce(s.nonTerminal, s.size)
                            } else CSyntacticException(UNRESOLVED_AMBIGUITY_DETECTED)
                        }
                    }
                    else actns += (i, s.lookahead) -> CReduce(s.nonTerminal, s.size)
                }
            })
        }

        nonTerminals foreach (c =>
        {
            for (i <- 0 until items.size)
            {
                val gt = goto(itms(i), c)
                val j = itmIndxs.getOrElse(gt, -1)
                if (j != -1) actns += (i, c) -> CGoTo(j)
            }
        })

        actns
    }

    private def items():Seq[CSituationSet] =
    {
        def items(collector:ArrayBuffer[CSituationSet], workset:mutable.HashSet[CSituationSet]):Seq[CSituationSet] =
        {
            val wrkst = mutable.HashSet[CSituationSet]()
            grammar foreach (c =>
            {
                workset foreach (ss =>
                {
                    val stnSt = goto(ss, c)
                    if (!stnSt.value.isEmpty && (collector contains stnSt unary_!))
                    {
                        collector += stnSt
                        wrkst += stnSt
                    }
                })
            })
            if (wrkst.isEmpty) collector else items(collector, wrkst)
        }

        val init = closure(CSituationSet(CSituation(start, 0, start.lookahead, 0) :: Nil))
        items(ArrayBuffer(init), mutable.HashSet(init))
    }

    private def first(category:CCategory):Iterable[CCategory] =
    {
        def first(collector:mutable.HashSet[CCategory], workset:mutable.HashSet[CCategory]):collection.Set[CCategory] =
        {
            val wrkst = mutable.HashSet[CCategory]()
            (workset.view
                filter (_.isInstanceOf[CNonTerminal])
                map (_.asInstanceOf[CNonTerminal])
                foreach (_.alternatives foreach (a =>
                {
                    val ctgr = a.head
                    if (collector contains ctgr unary_!)
                    {
                        collector += ctgr
                        wrkst += ctgr
                    }
                })))
            if (wrkst.isEmpty) collector else first(collector, wrkst)
        }

        firstCache.getOrElseUpdate(category, first(mutable.HashSet(category), mutable.HashSet(category)))
    }


    private def closure(situationSet:CSituationSet):CSituationSet =
    {
        def closure(collector:mutable.HashSet[CSituation], workset:mutable.HashSet[CSituation]):mutable.HashSet[CSituation] =
        {
            val wrkst = mutable.HashSet[CSituation]()
            workset.view filter (s => s.isMarkerInBounds && !s.isCurrentTerminal) foreach (s =>
            {
                val frsts = if (s.isMarkerPlusInBounds) first(s.currentPlus) else s.lookahead :: Nil
                (frsts.view
                    filter (_.isInstanceOf[CTerminal])
                    map (_.asInstanceOf[CTerminal])
                    foreach (f =>
                    {
                        for (i <- 0 until s.current.asInstanceOf[CNonTerminal].alternatives.size)
                        {
                            val stn = CSituation(s.current.asInstanceOf[CNonTerminal], i, f, 0)
                            if (collector contains stn unary_!)
                            {
                                collector += stn
                                wrkst += stn
                            }
                        }
                    }))
            })
            if (wrkst.isEmpty) collector else closure(collector, wrkst)
        }

        closuresCache.getOrElseUpdate(situationSet, CSituationSet(closure(mutable.HashSet() ++= situationSet.value, mutable.HashSet() ++= situationSet.value)))
    }

    private def goto(situationSet:CSituationSet, category:CCategory) =
    {
        gotoCache.getOrElseUpdate((situationSet, category),
        {
            val closures = ArrayBuffer[CSituation]()
            situationSet.value.view filter (s => s.isMarkerInBounds && s.current == category) foreach (s =>
                closures += CSituation(s.nonTerminal, s.index, s.lookahead, s.marker + 1))
            closure(CSituationSet(closures))
        })
    }
}

object CTable
{
    def apply(terminals:Seq[CTerminal], nonTerminals:Seq[CNonTerminal], start:CStart, priorities:collection.Map[(CCategory, CCategory), CCategory])
        = (new CTable(terminals, nonTerminals, start, priorities))()
}

trait CAction
case class CShift(state:Int) extends CAction
case class CReduce(category:CCategory, size:Int) extends CAction
case class CGoTo(state:Int) extends CAction
case class CAccept() extends CAction

case class CSituationSet(value:Iterable[CSituation])
{
    private val _toString = value.foldLeft("")(_ concat _.toString)
    private val _hashCode = _toString.hashCode

    override def toString = _toString
    override def hashCode = _hashCode
    override def equals(that:Any) = that != null && that.isInstanceOf[CSituationSet] && that.toString == toString
}

case class CSituation(nonTerminal:CNonTerminal, index:Int, lookahead:CTerminal, marker:Int)
{
    private val _toString = nonTerminal.name + index + lookahead.name + marker.toString
    private val _hashCode = _toString.hashCode

    def current = chain(marker)
    def currentPlus = chain(marker + 1)
    def size = chain.size
    def isMarkerInBounds = marker < chain.size
    def isMarkerPlusInBounds = marker + 1 < chain.size
    def isCurrentTerminal = current.isInstanceOf[CTerminal]
    def isCurrentNonTerminal = current.isInstanceOf[CNonTerminal]
    def isStart = nonTerminal.isInstanceOf[CStart]

    override def toString = _toString
    override def hashCode = _hashCode
    override def equals(that:Any) = that != null && that.isInstanceOf[CSituation] && that.toString == toString

    private def chain = nonTerminal.alternatives(index)

}
